package leetcode;

/**
 * Created with IntelliJ IDEA.
 * User: Ghost
 * Date: 14-5-29
 * Time: 下午7:19
 * To change this template use File | Settings | File Templates.
 */

import java.util.ArrayList;
import java.util.HashMap;

/**
 * Definition for a point.
 *
 */class Point {
         int x;
         int y;
         Point() { x = 0; y = 0; }
         Point(int a, int b) { x = a; y = b; }
     }
public class Solution3 {
    public String getK(Point A,Point B){
        if(A.x == B.x && A.y!=B.y)
        {
            return "";
        }
        else if(A.x == B.x && A.y == B.y){
            return "same";
        }
        else
            return String.valueOf((A.y-B.y)/(A.x-B.x));
    }
    public Point[] limitRedundent(Point[] points){
        ArrayList<Point> list = new ArrayList<Point>();
        for(int i=0;i<points.length;i++){
            list.add(points[i]);
        }
        for(int i=0;i<list.size();i++){
            for(int j=i+1;j<list.size();j++){
                if(list.get(j).x==list.get(i).x && list.get(j).y==list.get(i).y){
                    list.remove(j);
                    j-=1;
                }
            }
        }
        Point[] points1 = new Point[list.size()];
        points1 = list.toArray(points1);
        return points1;
    }
    public int maxPoints(Point[] points) {
        if(points.length == 0)
            return 0;
       // Point[] points1 = limitRedundent(points);
        HashMap<String,Integer> map = new HashMap<String, Integer>();
        int maxNum = 0;
        int MAX = 0;
        for(int i=0;i<points.length;i++){
            for(int j=0;j< points.length;j++){
                if(j==i)
                    continue;
                String k = getK(points[j],points[i]);

                if(k.length()==0){
                    k = "large";
                }
                if(map.get(k)!= null){

                    int num = map.get(k);
                    map.put(k,num+1);
                    if( !k.equals("same")&&(num+1)>maxNum){
                        maxNum = num+1;
                    }
                }
                else{
                    map.put(k,1);
                    if( !k.equals("same") && maxNum<1){
                        maxNum = 1;
                    }
                }
            }
            if(map.containsKey("same"))
                maxNum += map.get("same");
            System.out.println(maxNum);
            map.clear();
            if(MAX<maxNum)
                MAX = maxNum;
            maxNum = 0;
        }
        return (int) MAX;
    }
    public static void main(String[] args){
        Solution3 solution3 = new Solution3();
        Point[] points = new Point[4];
        points[1] = new Point(0,0);
        points[0] = new Point(0,0);
        points[2] = new Point(0,0);
        points[3] = new Point(0,0);
        System.out.println(solution3.maxPoints(points));
    }
}
